package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

/**
 * 对称的二叉树
 *
 * @author yuhushuan
 * @date 2020/6/20 11:04
 */
public class _28_1_SymmetricalBinaryTree {
    private static boolean isSymmetrical(BinaryTreeNode root) {
        if (root == null) {
            return false;
        }
        return isSymmetrical(root, root);
    }

    private static boolean isSymmetrical(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.value != root2.value) {
            return false;
        }
        // root1 左到右递归，root2 右到左递归
        return isSymmetrical(root1.left, root2.right)
                && isSymmetrical(root1.right, root2.left);
    }

    public static void main(String[] args) {
        // 功能测试
        test1();
        // 对称的二叉树
        // 结构不对称
        test2();
        // 结构对称，节点值不对称
        test3();

        // 特殊输入测试
        // 根节点为null
        print(null);
        // 只有一个节点的二叉树
        print(new BinaryTreeNode(1));
        // 所有节点的值都相同的二叉树
        test4();
    }

    private static void test1() {
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2_0 = new BinaryTreeNode(6);
        BinaryTreeNode n2_1 = new BinaryTreeNode(6);

        BinaryTreeNode n3_0 = new BinaryTreeNode(5);
        BinaryTreeNode n3_1 = new BinaryTreeNode(7);
        BinaryTreeNode n3_2 = new BinaryTreeNode(7);
        BinaryTreeNode n3_3 = new BinaryTreeNode(5);

        n1.left = n2_0;
        n1.right = n2_1;

        n2_0.left = n3_0;
        n2_0.right = n3_1;

        n2_1.left = n3_2;
        n2_1.right = n3_3;
        print(n1);
    }

    private static void test2() {
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2_0 = new BinaryTreeNode(6);
        BinaryTreeNode n2_1 = new BinaryTreeNode(6);

        BinaryTreeNode n3_0 = new BinaryTreeNode(5);
        BinaryTreeNode n3_1 = new BinaryTreeNode(7);
        BinaryTreeNode n3_2 = new BinaryTreeNode(7);
        BinaryTreeNode n3_3 = new BinaryTreeNode(5);

        n1.left = n2_0;
        n1.right = n2_1;

        n2_0.left = n3_0;
        n2_0.right = n3_1;

        n2_1.left = n3_2;
        print(n1);
    }

    private static void test3() {
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2_0 = new BinaryTreeNode(6);
        BinaryTreeNode n2_1 = new BinaryTreeNode(6);

        BinaryTreeNode n3_0 = new BinaryTreeNode(5);
        BinaryTreeNode n3_1 = new BinaryTreeNode(7);
        BinaryTreeNode n3_2 = new BinaryTreeNode(5);
        BinaryTreeNode n3_3 = new BinaryTreeNode(5);

        n1.left = n2_0;
        n1.right = n2_1;

        n2_0.left = n3_0;
        n2_0.right = n3_1;

        n2_1.left = n3_2;
        n2_1.right = n3_3;
        print(n1);
    }

    private static void test4() {
        BinaryTreeNode n1 = new BinaryTreeNode(7);
        BinaryTreeNode n2_0 = new BinaryTreeNode(7);
        BinaryTreeNode n2_1 = new BinaryTreeNode(7);

        BinaryTreeNode n3_0 = new BinaryTreeNode(7);
        BinaryTreeNode n3_1 = new BinaryTreeNode(7);
        BinaryTreeNode n3_2 = new BinaryTreeNode(7);
        BinaryTreeNode n3_3 = new BinaryTreeNode(7);

        n1.left = n2_0;
        n1.right = n2_1;

        n2_0.left = n3_0;
        n2_0.right = n3_1;

        n2_1.left = n3_2;
        print(n1);
    }

    private static void print(BinaryTreeNode root) {
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        System.out.println("是对称二叉树为：" + isSymmetrical(root));
        System.out.println();
    }


}
